package com.atguigu.dynamic;

import java.util.Arrays;

/** 背包问题 */
public class KnapsackProblem1 {

    public static void main(String[] args) {
        String[] name = { "吉他", "音响", "电脑" };
        // 背包对应的重量
        int[] weight = { 1, 4, 3 };
        // 背包对应的价值
        int[] val = { 1500, 3000, 2000 };
        int wn = 4;
        int vn = 3;

        int[][] vList = new int[vn+1][wn+1];
        int[][] pathList = new int[vn+1][wn+1];

        // 第一步,初始化vlist
        for (int i = 1; i < vn+1; i++) {
            for (int j = 1; j < wn+1; j++) {
                // int max=Math.max(val[i], vList[i][j-1]+vList[i][j-2]);
                // 获取的重量要少于j
                if (weight[i-1] > j) {
                   // vList[i][j] = val[i-1];

                    vList[i][j] = vList[i-1][j];
                 
                } 
                else if(weight[i-1] <=j)
                {
                    // vList[i][j] = val[i-1];
                    if(vList[i-1][j] < val[i-1]+vList[i-1][j - weight[i - 1]])
                    {
                    vList[i][j]=val[i-1]+vList[i-1][j - weight[i - 1]];
                    pathList[i][j]=1;
                    }
                     else {
                        vList[i][j] = vList[i-1][j];
                    }
                }
                
               
                
            }
        }

        for (int[] item : vList) {
            System.out.println(Arrays.toString(item));
        }

        System.out.println("------------");
        for (int[] item : pathList) {
            System.out.println(Arrays.toString(item));
        }

    }
}